import java.util.HashMap;

public class HeapSort2 {
    public static void main(String[] args) {
        int[] nums = new int[]{3,2,1,5,6,4};
        HeapSort(nums);
        for (int num : nums) {
            System.out.print(num + " ");
        }
        //System.out.println(nums[nums.length-2]);
    }

    static void HeapSort(int[] arr){
        BuidHeap(arr);
        for(int i=arr.length-1;i>=1;i--){
            int t = arr[i];
            arr[i]=arr[0];
            arr[0]=t;
            Heapify(arr,0,i-1);
        }
    }
    //堆创建
    static void BuidHeap(int[] arr){
        for (int i=arr.length/2-1;i>=0;i--){
            Heapify(arr, i,arr.length-1);
        }

    }
    //堆调整
    static void Heapify(int[] arr,int index,int len){
        int leftson = (index<<1)+1;
        int rightson = (index<<1)+2;
        int temp=0;
        if(leftson<=len && rightson<=len){
            //求左右孩子节点的最大值
            temp = arr[leftson]>arr[rightson]?leftson:rightson;
        }
        else if(leftson<=len){
            temp = leftson;
        }
        else if(rightson<=len){
            temp = rightson;
        }
        else return;

        if(arr[index]<arr[temp]){
            int t= arr[index];
            arr[index] = arr[temp];
            arr[temp] = t;
            Heapify(arr,temp,len);
        }
    }

}
